107 台大計系
Computer Architecture
1
a. please explain what architecture support is needed for this.
- programs 可以並行執行
- program之間通常不能互相讀取
想到Virtual Memory
- page table - 每個process有自己的page table，OS分配記憶體和更新page table，process之間便不會衝突，即可實現這兩點
- MMU - 需要一個額外硬體轉換VA→PA
Operating System 9th pg.376 - We first need to make sure…
Computer Architecture 5th pg.44 - what is architecture?
Computer Orgnization 5th pg.432 - why page table?
lw $t0, 20($s2)
addu $t1, $t0, $t2
sub $s4, $s4, $t3
在 in-order execution 情況下，即使 sub 與 lw、addu 沒有資料相依， sub 仍必須等待，如果 lw 發生 cahce miss 的話，要存取 memory 拿資料，可能會花費相當多 clock cycle，OOOE 可以避免這種情況。
張凡課本下冊，動態多重分發處理器
c. 解釋 speculatively 的優缺點
張凡課本下冊，speculation
d. 造成例外的原因，現代處理器如何處理 out-of-order 造成的例外及正確性
- 造成原因
- interrupt
- TLB miss
- cache miss…etc
- 如何處理?
- in-order execution
找出那個 instruction 發生 exception，並以此為交界線，在這之前的要執行完，在這之後的全都 flush
- OOOE
1.仍然保持對 instruction 的順序標記，以方便控制哪個要執行哪個要flush
2.全部flush
https://www.cs.virginia.edu/~cr4bd/3330/S2017/notes/20170316-part2-slides-1up.pdf
e. 解釋 cache 的重要性，及為何 cache data 會有不同
- cache重要在於，memory為Von Neumann model的瓶頸，搬資料的速度相對CPU來說太慢了。
- 為何不同？
http://www.cc.ntu.edu.tw/chinese/epaper/0045/201806204508.html
2
(f)
每台電腦需處理 1015NBytes，每個 disk 裝 1015NDBytes，transfer rate 250MB/sec
- min : seek 一次
- 5(ms)+1015ND250M(sec)=4∗106ND(sec)
- max : 每個 block 都 seek 一次
- 需 1012ND 個 block
- 5∗1012ND(ms) + 1015ND250M(sec)=5.004∗109ND (sec)
(g)
- 1015N8∗(16∗230) = 213N (sec)
(h)
- 兩兩合併 類似 full binary tree 結構
- 100∗lgN
(i)
- 所需時間 : (f)>(g)>(h) → 可透過換成 SSD 來改善
3 Which processor below isn’t affected by Meltdown?
( C ) - intel Itanium
張凡課本下冊，VLIW
4
5 Which statement below is FALSE…?
(b) - 是8-bit 不是32-bit
https://cloud.google.com/blog/products/gcp/an-in-depth-look-at-googles-first-tensor-processing-unit-tpu
6 Which … does’t exploit parallelism?
(b)
a. ILP
b. none
c. ILP (superscalar)
d. TLP、DLP
張凡課本，定義ILP
Computer Orgnization 5th pg.525
Computer Architecture 5th pg.38
7 Branch prediction is more important…
(T)
- 隨著pipeline stage增加，從IF到branch決定的stage越長的話，表示要flush的instruction
越多
張凡課本，control hazard
8 Two instructions … may not cause data hazard…
(T)
張凡課本，data hazard
9 If VIPT is used, one RAM data…
(F)
張凡課本，virtual index virtual tag(VIVT)
Operating System
10
a
- TLB為page table的cache
- 目的是為了節省每次都要去存取在memory的page table的時間
- CPU產生VA
- 餵給TLB
- hit的話，將PA餵給Cache
miss的話 ，將原來的VA餵給page table找到PA
┌───┐ ┌───┐hit┌────┐
│CPU │→│TLB │-→│Cache│
└───┘ └───┘ – └────┘
TLB miss↓
┌───────┐
│page table│
└───────┘
張凡課本，TLB
b 1.F12C 2.2A9D 3.Page fault
c inverted page table && multilevel page table
- 不能更換CPU
- possible method
每一次mode switch的時候，都把TLB清空以確保user mode不會使用到kernel mode的PPN
- The performance impacts
每一次mode switch都要重新填滿TLB，如果mode switch極度頻繁時，等同於沒有TLB這個元件，都要去放在momory的page table拿PPN。
→單一instruction/data的latency會提高，AMAT加一個memory access
Operating System 9th pg.374
https://stackoverflow.com/questions/21887797/what-is-the-overhead-of-a-context-switch
CFQ, deadline(恐龍書上只提到 CFQ )
理論上紅黑樹為一棵 balanced tree，在上面 search、delete 只要花費 O(lg n) 的時間
補充：
- CFQ(completely fair scheduler)
I/O scheduler，用 rtree 紀錄 I/O request 與 priority。
- deadline
用來保證 I/O request 在一定時間內被服務，以避免 starvation。
- noop
採用 FIFO 法則，早期(2.4版)以前只有這個 scheduler
https://lwn.net/Articles/184495/
https://www.infradead.org/~mchehab/kernel_docs/unsorted/rbtree.html
12
13
實際舉硬碟排班例子 (1)FCFS會比SSTF優的 (2)FCFS比SSTF差
-
<這個要湊的話技巧就是讓SSTF要一直折返來折返去的，而FCFS順順的跑就好>
- (1)現在硬碟總共有0~99(track) 目前在50
TRACK要求順序:48.51.55
FCFS:50->48->51->55 所以距離是:2+7=9
SSTF:50->51->48->55 距離是1+3+7=11
-
<基本上SSJF都會比FCFS好，所以這很好湊>
- (2)現在硬碟總共有0~99(track) 目前在50
TRACK要求順序:60.52
FCFS:50->62->52 所以距離是:22
SSJF:50->52->60 距離是:10
14 Binary Semaphore to Counting Semaphor
Semaphore S1,S2
int c
wait(S)
{
wait(s1);
c = c-1;
if (c < 0)
{
signal(s1);
wait(s2);
}
else signal(s1);
}
signal(s)
{
wait(s1);
c = c+1;
if(c <= 0)
{
signal(s2);
}
signal(s1);
}
107 台大計系
Computer Architecture
1
a. please explain what architecture support is needed for this.
想到Virtual Memory
Operating System 9th pg.376 - We first need to make sure…
Computer Architecture 5th pg.44 - what is architecture?
Computer Orgnization 5th pg.432 - why page table?
b. please explain out-of-order execution(OOOE) is indispensable performance feature on modern processors.
lw $t0, 20($s2) addu $t1, $t0, $t2 #load-use ，用forwarding仍需花費one cycle stall sub $s4, $s4, $t3張凡課本下冊，動態多重分發處理器
c. 解釋 speculatively 的優缺點
張凡課本下冊，speculation
d. 造成例外的原因，現代處理器如何處理 out-of-order 造成的例外及正確性
找出那個 instruction 發生 exception，並以此為交界線，在這之前的要執行完，在這之後的全都 flush
1.仍然保持對 instruction 的順序標記，以方便控制哪個要執行哪個要flush
2.全部flush
https://www.cs.virginia.edu/~cr4bd/3330/S2017/notes/20170316-part2-slides-1up.pdf
e. 解釋 cache 的重要性，及為何 cache data 會有不同
http://www.cc.ntu.edu.tw/chinese/epaper/0045/201806204508.html
2
(f)
每台電腦需處理1015NBytes ，每個 disk 裝 1015NDBytes ，transfer rate 250MB/sec
(g)
(h)
(i)
3 Which processor below isn’t affected by Meltdown?
( C ) - intel Itanium
張凡課本下冊，VLIW
4
5 Which statement below is FALSE…?
(b) - 是8-bit 不是32-bit
https://cloud.google.com/blog/products/gcp/an-in-depth-look-at-googles-first-tensor-processing-unit-tpu
6 Which … does’t exploit parallelism?
(b)
a. ILP
b. none
c. ILP (superscalar)
d. TLP、DLP
張凡課本，定義ILP
Computer Orgnization 5th pg.525
Computer Architecture 5th pg.38
7 Branch prediction is more important…
(T)
越多
張凡課本，control hazard
8 Two instructions … may not cause data hazard…
(T)
張凡課本，data hazard
9 If VIPT is used, one RAM data…
(F)
張凡課本，virtual index virtual tag(VIVT)
Operating System
10
a
miss的話 ，將原來的VA餵給page table找到PA
┌───┐ ┌───┐hit┌────┐
│CPU │→│TLB │-→│Cache│
└───┘ └───┘ – └────┘
TLB miss↓
┌───────┐
│page table│
└───────┘
張凡課本，TLB
b 1.F12C 2.2A9D 3.Page fault
c inverted page table && multilevel page table
d Please discribe possible method… and discuss the performance
每一次mode switch的時候，都把TLB清空以確保user mode不會使用到kernel mode的PPN
每一次mode switch都要重新填滿TLB，如果mode switch極度頻繁時，等同於沒有TLB這個元件，都要去放在momory的page table拿PPN。
→單一instruction/data的latency會提高，AMAT加一個memory access
Operating System 9th pg.374
https://stackoverflow.com/questions/21887797/what-is-the-overhead-of-a-context-switch
11 In Linux scheduler, what performance is improved using red-black-tree …
CFQ, deadline(恐龍書上只提到 CFQ )
理論上紅黑樹為一棵 balanced tree，在上面 search、delete 只要花費 O(lg n) 的時間
補充：
I/O scheduler，用 rtree 紀錄 I/O request 與 priority。
用來保證 I/O request 在一定時間內被服務，以避免 starvation。
採用 FIFO 法則，早期(2.4版)以前只有這個 scheduler
https://lwn.net/Articles/184495/
https://www.infradead.org/~mchehab/kernel_docs/unsorted/rbtree.html
12
13
實際舉硬碟排班例子 (1)FCFS會比SSTF優的 (2)FCFS比SSTF差
<這個要湊的話技巧就是讓SSTF要一直折返來折返去的，而FCFS順順的跑就好>
TRACK要求順序:48.51.55
FCFS:50->48->51->55 所以距離是:2+7=9
SSTF:50->51->48->55 距離是1+3+7=11
<基本上SSJF都會比FCFS好，所以這很好湊>
TRACK要求順序:60.52
FCFS:50->62->52 所以距離是:22
SSJF:50->52->60 距離是:10
14 Binary Semaphore to Counting Semaphor
Semaphore S1,S2 int c wait(S) { wait(s1); c = c-1; if (c < 0) { signal(s1); wait(s2); } else signal(s1); } signal(s) { wait(s1); c = c+1; if(c <= 0) { signal(s2); } signal(s1); }